import { IIterator } from "../types";
import BaseLinkList from "./base";
import { Node } from './singleLinkList'


/**
 * 单向循环链表
 * 链表实现
 */
class SingleCycleLinkedList<T = number> extends BaseLinkList<T> {
    private sizes: number = 0
    private root: Node<T> | null = null

    /**
     * 获取根元素
     */
    getRoot() {
        return this.root;
    }

    /**
     * 获取链表中元素的数量
     */
    size() {
        return this.sizes;
    }

    /**
     * 链表是否为空
     */
    isEmpty() {
        return this.sizes === 0
    }

    /**
     * 链表是否包含元素T
     * @param element 
     */
    contains(element: T) {
        return this.indexOf(element) !== -1
    }

    /**
     * 添加元素到尾部
     * @param element 
     */
    add(element: T) {
        // 检验element
        this.checkElement(element);

        this.addToIndex(this.sizes, element);
    }

    /**
     * 添加元素到索引位置
     * @param index 
     * @param element 
     */
    addToIndex(index: number, element: T) {
        const sizes = this.sizes;
        if (index < 0 || index > sizes) {
            throw new Error('索引越界~~')
        }

        // 首次添加
        if (sizes === 0) {
            this.root = new Node(element, null);
            this.sizes++
            return
        }

        if (index === 0) {
            // 添加首部

            const root = this.root;
            const newNode = new Node(element, root);

            // 改变最后一个元素的next首元素 
            const lastEle = this.getLastEle();
            lastEle.next = newNode;

            // 重新改变node的指向
            this.root = newNode;

        } else if (index === sizes) {
            // 添加到尾部
            // 获取最后一个元素
            const lastEle = this.getLastEle();
            // 添加到最后
            lastEle!.next = new Node(element, this.root);
        } else {
            // 添加到中间位置
            this.iterator((node, i, prevNode) => {
                if (i === index) {
                    const newNode = new Node(element, node);
                    // 前一个的next指向新的节点
                    prevNode!.next = newNode;
                    return true;
                }
                return false
            })

        }
        this.sizes++;

    }

    /**
     * 往队头添加元素
     * @param element 
     */
    unshift(element: T) {
        if (this.isEmpty()) return 0;
        this.addToIndex(0, element);
        return this.sizes;
    }

    /**
     * 删除对头元素并删除
     */
    shift() {
        if (this.isEmpty()) return null;
        return this.remove(0);
    }

    /**
     * 删除队尾元素并取出
     */
    pop() {
        // 空的
        if (this.isEmpty()) return null;
        return this.remove(this.sizes - 1)
    }

    /**
     * 获取index处的元素
     * @param index 
     */
    get(index: number) {
        // 链表为空
        if (this.isEmpty()) return;
        this.checkIndex(index);
        let val: Node<T> | null = null
        this.iterator((node, i) => {
            if (index === i) {
                val = node;
                return true;
            }
            return false
        })

        return val!
    }

    /**
     * 修改index处的元素为element
     * @param index 
     * @param element 
     */
    set(index: number, element: T) {
        // 检验参数
        this.checkIndex(index);
        this.checkElement(element);

        this.iterator((node, i) => {
            if (i === index) {
                node.value = element
                return true
            }
            return false
        })

        return element
    }

    /**
     * 获取元素T的索引
     */
    indexOf(element: T) {
        this.checkElement(element);
        let i = -1;
        this.iterator((node, index) => {
            // 元素相等
            if (node.value === element) {
                i = index
                return true;
            }
            return false
        })
        return i
    }

    /**
     * 根据index获取节点
     * @param index 
     */
    private node(index: number): Node<T> {
        let n!: Node<T>;
        this.iterator((node, i) => {
            if (i === index) {
                n = node;
                return true
            }
            return false;
        })
        return n
    }

    /**
     * 从链表中删除element
     * @param element 
     */
    remove(index: number) {
        if (this.isEmpty()) return null
        // 校验element
        this.checkIndex(index)
        const element = this.node(index);
        if (index === 0) {
            // 删除的是根元素
            this.root = element.next;
            // 获取最后一个元素
            const lastEle = this.getLastEle();
            lastEle.next = element.next;

        } else {
            // 获取前一个元素
            const prev = this.node(index - 1)
            prev.next = element.next;
        }
        this.sizes--;
        return element.value!;
    }

    /**
     * 获取最后一个元素
     */
    private getLastEle() {
        let i = 0,
            sizes = this.sizes,
            root = this.root!;
        for (; i < sizes - 1; i++) {
            root = root?.next!;
        }

        return root
    }


    /**
     * 清空链表
     */
    clear() {
        // 清空
        this.sizes = 0;
        this.root = null;
    }

    /**
     * 链表迭代器
     */
    forEach(cb: IIterator<T>) {
        if (this.isEmpty()) return;
        this.iterator((node, i) => {
            cb(node.value!, i)
            return false
        })
    }

    /**
     * 遍历链表
     * @param cb 
     */
    private iterator(cb: (node: Node<T>, index: number, prevNode: Node<T> | null) => boolean) {
        let i = 0,
            sizes = this.sizes,
            root = this.root,
            prevNode = null;

        for (; i < sizes; i++) {
            // root没有next 或者 cb停止遍历了
            if (root!.value === null || cb(root!, i, prevNode)) break;
            prevNode = root;
            root = root!.next;
        }
    }

    /**
     * 检验元素的合法性
     * @param element 
     */
    private checkElement(element: T) {
        if (element == null) {
            throw new Error('元素不能为空~~')
        }
    }

    /**
     * 校验索引
     * @param index 
     */
    private checkIndex(index: number) {
        if (index < 0 || index >= this.sizes) {
            throw new Error('索引越界~~')
        }
    }

}

export default SingleCycleLinkedList;